#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>
#include<unordered_map>
using namespace std;
class LRUCache {
public:
    LRUCache(int capacity) :_capacity(capacity)
    {
        hash.reserve(_capacity);
    }

    int get(int key)
    {
        auto ret = hash.find(key);
        if (ret == hash.end()) return -1;
        else
        {
            auto node = ret->second;
            list.splice(list.begin(), list, node);
            return node->second;
        }

    }

    void put(int key, int value)
    {
        auto ret = hash.find(key);
        if (ret != hash.end())
        {
            auto node = ret->second;
            list.splice(list.begin(), list, node);
            node->second = value;
        }
        else
        {
            if (hash.size() == _capacity)
            {
                hash.erase(list.back().first);
                list.pop_back();
            }
            list.emplace_front(key, value);
            hash[key] = list.begin();
        }
    }

private:
    int _capacity = 0;
    unordered_map<int, list<pair<int, int>>::iterator> hash;
    list<pair<int, int>> list;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */